// map.hpp
// Map, an unordered key->value collection.
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef R_MAP_HPP
#define R_MAP_HPP

#include "standard.hpp"
#include "adts/iterator.hpp"

namespace Ripe {
  enum BucketType {
    BucketEmpty, // Bucket clean, never held an item,
    BucketLazy,  // Bucket had an item in it, but it was lazily removed,
    BucketFull
  };

  template <class K, class V>
  class Bucket{
    public:
      BucketType type;
      K key;
      V value;
  };

  // Map doesn't contain that key
  class ErrorKey : public Exception {};

  template <class K, class V>
  class MapIterator;

  // Default number of elements in a map:
  #ifndef R_MAP_DEFAULT_SIZE
  #define R_MAP_DEFAULT_SIZE 2
  #endif
  
  template <class K, class V>
  class Map {
    public:
      // Construct a map preallocated with space for n items.
      Map(uint32_t n = R_MAP_DEFAULT_SIZE);
      
      // Deallocate the contents of the map.
      ~Map();

      // Number of key->value pairs in the map.
      uint32_t size;

      // Lookup the given key.
      // If it is found, return true. Place the value into the location pointed
      // to by value.
      //
      // If key is not found, location at value is not changed.
      bool get(K key, V* value);

      // Like get() above, but throws an exception if the key is not found.
      V get(K key) throw(ErrorKey);

      // Set a key->value pair.
      bool set(K key, V value);

      // Output a graphical representation of the map.
      void  print();

    private:
      friend class MapIterator<K,V>;
    
      // Number of buckets allocated.
      uint32_t alloc_size;

      Bucket<K,V>* data;

      // Internal: Set a key->value pair in the given size-many buckets.
      bool set2(Bucket<K,V>* buckets, uint32_t size, K key, V value);
      
      // Internal: Allocate the buckets
      Bucket<K,V>* allocate(uint32_t n);
  };
  
  template <class K, class V>
  class MapIterator : public TwoIterator<K,V> {
    public:
      MapIterator();
    
      MapIterator(Map<K,V>* m);
                  
      bool has_more();
      
      void get(K* one, V* two);
      
      void reset(Map<K,V>* m);
      
    private:
      Map<K,V>* map;
      uint32_t idx;
      bool more;
      void find_next();
  };
}

#include "map.cpp"

#endif // R_MAP_HPP
